package org.lql.algo.codecrush.week002;

/**
 * @author: liangqinglong
 * @date: 2025-07-29 16:21
 * @description: 面试题 16.04. 井字游戏 <a href="https://leetcode.cn/problems/tic-tac-toe-lcci/description/">...</a>
 **/
public class Tictactoe {

    /**
     * 设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
     * <p>
     * 以下是井字游戏的规则：
     * <p>
     * 玩家轮流将字符放入空位（" "）中。
     * 第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
     * "X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
     * 当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
     * 当所有位置非空时，也算为游戏结束。
     * 如果游戏结束，玩家不允许再放置字符。
     * 如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
     * <p>
     * 示例 1：
     * <p>
     * 输入： board = ["O X"," XO","X O"]
     * 输出： "X"
     * 示例 2：
     * <p>
     * 输入： board = ["OOX","XXO","OXO"]
     * 输出： "Draw"
     * 解释： 没有玩家获胜且不存在空位
     * 示例 3：
     * <p>
     * 输入： board = ["OOX","XXO","OX "]
     * 输出： "Pending"
     * 解释： 没有玩家获胜且仍存在空位
     * 提示：
     * <p>
     * 1 <= board.length == board[i].length <= 100
     * 输入一定遵循井字棋规则
     */
    public String tictactoe(String[] board) {
        int n = board.length;
        int[] row = new int[n];
        int[] col = new int[n];
        // 记录主对角线和副对角线的累计得分
        int diag = 0;      // 左上 → 右下
        int antiDiag = 0;  // 右上 → 左下
        boolean hasEmpty = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char c = board[i].charAt(j);
                if (c == ' ') {
                    hasEmpty = true;
                    continue;
                }
                // O 记为 +1，X 记为 -1
                int delta = c == 'O' ? 1 : -1;
                // 更新当前行、列的统计值
                row[i] += delta;
                col[j] += delta;
                // 如果在主对角线上
                if (i == j) {
                    diag += delta;
                }
                // 如果在副对角线上
                if (i + j == n - 1) {
                    antiDiag += delta;
                }
                // 如果当前某一行、列或对角线已经被某个玩家占满
                if (Math.abs(row[i]) == n || Math.abs(col[j]) == n || Math.abs(diag) == n || Math.abs(antiDiag) == n) {
                    return delta == 1 ? "O" : "X";
                }
            }
        }
        return hasEmpty ? "Pending" : "Draw";
    }

    public static void main(String[] args) {
        String[] board = {"O X", " XO", "X O"};
        Tictactoe tictactoe = new Tictactoe();
        String result = tictactoe.tictactoe(board);
        System.out.println(result);

        board = new String[]{"OOX", "XXO", "OXO"};
        System.out.println(tictactoe.tictactoe(board));

        board = new String[]{"OOX", "XXO", "OX "};
        System.out.println(tictactoe.tictactoe(board));
    }
}
